The Monte Carlo method provides approximate solutions to mathematical problems by performing statistical sampling calculations on a computer. The method was developed originally during the middle 1940's as part of research for the atomic bomb program at Los Alamos. It can be used for problems which are inherently probabilistic and for problems that are apparently deterministic. An example of the former is the simulation of random neutron diffusion in a nuclear reactor. An example of the latter is the calculation of the energy levels of a quantum system. The Monte Carlo method is a standard tool in the science and finance fields. An overview of the Monte Carlo method which includes detailed explanations of the examples above is M. H. Kalos and P. A. Whitlock, "Monte Carlo Methods Volume I: Basics," pp. 7-37 (Wiley, New York, 1986).
The Monte Carlo method is widely used for many applications in scientific research, applied technology and finance. These include but are not limited to: simulation of the thermal properties of materials such as magnets and superconductors; simulation of the properties of industrially important polymer molecules such as polyethylene and proteins; the valuation of derivative securities such as interest rate derivatives or mortgage-backed securities; the estimation of the risk inherent in a portfolio of diverse financial instruments such as stocks, bonds, commodities and options; and the generation of realistic three-dimensional graphical images.
In such applications and others, the Monte Carlo method is used to estimate a statistical quantity appropriate for the application: typically this is an average value of a quantity computed with respect to a known probability distribution. The Monte Carlo method can also be used to provide estimates of the value of integrals of any dimension. The output from all of the calculations described above is usually either displayed on a computer screen or printed.
In the case of financial applications, such as interest-rate derivatives or mortgage backed securities, the Monte Carlo method is used because the complexity of the transactions and cash flows in the specification of the derivative security in question prevents the use of known alternative, faster methods of derivative valuation. Indeed, it is a generally held view that the Monte Carlo method is the most dependable and versatile technique at the disposal of practitioners in financial derivatives, and one robust enough so it may always be used if alternative techniques fail for any reason.
In many cases of practical interest, it is possible to equate the results of the Monte Carlo method to the solution of an appropriate differential equation associated with the statistical properties of the application of interest. When this can be done, it is advantageous if the speed of calculation is important to the user, because the differential equation is typically solvable by so-called lattice or finite-difference methods, known to those skilled in the art. In the particular context of financial applications, these lattice methods are known as tree methods, and are described by Jon C. Hull, "Options, Futures and Other Derivative Securities, 2d. Ed.," Chpt. 14 (Prentice Hall, Englewood Cliffs, 1993). The tree methods and the Monte Carlo method are completely equivalent mathematically, but differ in the manner of implementation.
Monte Carlo problems are typically formulated as multi-dimensional integrals, which without loss of generality can be taken to be over a unit hypercube. For example, the value of a derivative security can be represented as an integral over a multi-dimensional unit cube, as shown by S. H. Paskov and J. F. Traub, Journal of Portfolio Management, pp. 113-120, (Fall 1995). The dimension of the cube is determined by the underlying stochastic processes and the number of discrete time intervals involved in the specification of the derivative security.
The evaluation of an integral by the Monte Carlo method is performed by (i) choosing a number, N, of points at random in the multi-dimensional cube; (ii) evaluating the integrand at those points; and (iii) averaging the value of the integrand at those points to obtain the estimate of the integral. Thus the Monte Carlo estimate of the integral: EQU I=.function.f(x)d.sup.D x
of a function f(x), where x is a point in a D-dimensional hypercube, is given by the large N limit of: ##EQU1##
where the sum runs from i=1 to N and x.sub.1 is a sequence of random points in the D-dimensional hypercube. In present integrations performed on a digital computer, the points are chosen from a pseudo-random sequence generation program, such as those provided with many compilers. An example is the "rand ()" function provided with draft compliant ANSI C++ language.
Monte Carlo problems can also be formulated directly as simulations of the underlying stochastic process. For example, as is well known to those skilled in the art, and explained by John C. Hull, "Options, Futures and Other Derivative Securities 2d. Ed.," pp. 330-331 (Prentice Hall, Englewood Cliffs, 1993), the behavior of a stock price over time is sometimes modeled as random fluctuations superimposed on a steadily increasing average price. The time series for the change in value of the stock at the end of the day over a particular set of (e.g. 360) consecutive trading days constitutes a realization or particular scenario of the random price movements. In the following 360 day period the time series for the stock price movements would follow a different scenario. A derivative security whose value is some predetermined function of the stock price will have a value at the end of each 360 day period which in general depends upon the entire time series for the stock during each scenario. The average value for the derivative security 360 days from a given date can be calculated by simulating on a computer a large number N (e.g. 10,000) scenarios of the stock price movement which are statistically consistent with the known behavior or model of the stock price, calculating the value of the derivative security at the end of each scenario, and averaging the results. In this example, this procedure would be mathematically equivalent to performing a multidimensional integral in 360 dimensions.
The procedures described above will converge to the correct result if N is sufficiently large, but the rate of convergence is relatively slow. For example, the root-mean-square-error between the estimate after N points and the correct result decreases in proportion to 1l/N, independent of the dimension of the cube. In financial derivatives, some securities may require values of N as large as 10 million in order to achieve satisfactory accuracy. Such large calculations can take several hours on a personal computer having a Pentium type processor. Such lengthy time delays prevent derivative dealers from providing clients with real-time prices for these securities and thus may result in lost sales or trading opportunities and may also result in trades that are not based on real time information.
Thus, it is desirable to improve the rate of convergence of the estimate to obtain real-time pricing solutions. It has been found that this may be accomplished by replacing the pseudo-random sequence of points with an alternative sequence of points with appropriate properties. Deterministic sequences which cover the multi-dimensional cube more efficiently than pseudo-random sequences exist, and are generically termed low-discrepancy sequences. Examples of low-discrepancy sequences in the public domain include the Halton sequence, the Sobol sequence and the Faure sequence, all of which have been used to some extent to improve multi-dimensional integration. A detailed account of these developments is given by W. J. Morokoff and R. E. Caflisch, "Quasi-Monte Carlo Integration", 122 J. Comp. Phys. 218-230 (1995).
The low discrepancy sequences are determined purely by the dimension of the space, with such sequences being independent of the integrand. Integration using these sequences results in a convergence that varies approximately in proportion to 1/N for a large enough N. Thus, the use of the low discrepancy sequences can reduce calculation times. However, such times are still sometimes inadequate to meet the needs of rapidly changing financial transactions.
Other sequences also exist which can improve the convergence of Monte Carlo simulation. These sequences are valuable due to their superiority to low discrepancy sequences in accelerating integral evaluation programs and are often proprietary. Proprietary sequences may be generated in one of two ways: (i) in a manner independent of the integrand, or (ii) in a manner that is adapted in some way to the integrand. Such sequences are termed non-adaptive and adaptive, respectively. Non-adaptive sequences improve the convergence of the Monte Carlo simulation in a generic way: they work regardless of the integrand. Adaptive sequences improve the convergence of Monte Carlo simulation by exploiting the properties of the actual integrand. Thus, adaptive sequences potentially provide a much greater enhancement than non-adaptive sequences, because they construct a sequence specially targeted towards the integrand of interest.
The enhancement provided by adaptive techniques is potentially more consistent across different security types than that provided by non-adaptive techniques. This is because adaptive techniques are able to select the part of a sequence where the largest contributions to an integral are made and thus focus the sequence on these points. A non-adaptive method must provide points across the entire sequence. An example of a non-adaptive proprietary sequence is that used by IBM in its "Deterministic Simulation Blaster" (see P. Truel, "From IBM: Help in Intricate Trading," New York Times, Sep. 25, 1995). An example of an adaptive proprietary sequence is that used by NumeriX LLC in its C++ object-oriented software library.
In addition to evaluating integrals, the Monte Carlo method can be used to estimate the risk of a particular portfolio. The commonly accepted measure of risk is known as "Value-at-Risk." Over a predetermined time interval, and with a specified probability distribution for the independent random factors that determine the value of a portfolio of securities (e.g., foreign exchange rates, interest rates, stock prices, and others), the Value-at-Risk is the maximum loss that a portfolio would suffer with a given confidence level. The confidence level is often 95%; thus, in a particular instance, it might be said that a certain portfolio has a Value-at-Risk of U.S. $10 million at the 95% confidence level for the next day. This would imply that over the next day, there is a one-in-twenty chance that the portfolio would lose more than U.S. $10 million.
Value-at-Risk is calculated by the Monte Carlo method. A number, N, of scenarios are generated at random. Each scenario is a vector whose components are the random factors determining the value of the portfolio. The portfolio is evaluated at the scenarios, and a histogram of values is created. From the histogram, the present value of the portfolio can be subtracted, so that the histogram describes the profit and loss of the portfolio over the time period in question; i.e. the histogram records how many scenarios corresponded to a given amount of change in the value of the portfolio. Integrating this distribution allows one to determine the loss value which 5% of the scenarios exceed. This is the desired Value-at-Risk. A detailed account of the use of this measure in practice is given by P. Jorion, "Value at Risk," Chpt. 12 (Irwin, Chicago, 1996).
Both public-domain and proprietary non-adaptive sequences have been used to evaluate derivative securities. The results of the use of such sequences have been documented by several authors such as R. E. Caflisch and W. J. Morokoff "Valuation of Mortgage Backed Securities Using the Quasi-Monte Carlo Method," Proc. Stanford Conference on Computational Finance (August 1996); S. Paskov and J. F. Traub "Faster Valuation of Financial Derivatives," Journal of Portfolio Management, 113-120, Fall (1995).
Development of proprietary sequence generation programs can be expensive and time consuming as the integrand must be analyzed to determine what points in a sequence are most effective in accelerating the evaluation process. Such specially tailored sequence programs are difficult to obtain commercially because they require specific knowledge of the underlying integral evaluation program. The knowledge of the underlying integral evaluation program in the financial field is considered proprietary and thus not available.
A very commonly encountered situation is where a user owns a computer program which evaluates a particular derivative security by Monte Carlo simulation. However, the precise details of the security are proprietary in the sense that either the type of security being evaluated is confidential, or the assumptions of the derivative security model are proprietary. An example of the former situation is when a bank is trading a particular derivative security, but may not wish this fact to be known to other market participants. Secrecy in this case is desirable because the bank would seek to prevent other parties from imitating their trading strategy and thus potentially diminish its profitability.
An example of the latter situation is when a bank values interest-rate derivatives using a proprietary model for the term structure of interest rates. The better predictive power of such a model allows a bank to offer more competitive deals to clients. Such models are expensive to develop and can be, and generally are, treated as valuable trade secrets. In addition, the bank's trading strategies may rely on its superior modeling of the yield curve for a particular derivative security.
Accelerating the computation of a valuation program using non pseudo-random sequences which do not jeopardize secrecy involves either: (i) using sequences that are in the public domain, or (ii) developing in-house sequences, which may be either non-adaptive or adaptive. The public domain sequences often do not achieve the desired level of acceleration because they cannot take advantage of the characteristics of the integrand. Developing in-house sequencing programs is expensive and time consuming, especially in view of the expense of developing the initial valuation program.
Other options jeopardize the secrecy of the proprietary valuation programs. These options include: (i) disclosing the proprietary valuation code to a party which is already in possession of proprietary sequences, or (ii) allowing the party in possession of proprietary sequences access to a public domain valuation code. As explained above, the first option is undesirable because it jeopardizes the secrecy of the valuation program. In the second case the improved code can be used for valuation purposes, but may not maximize the acceleration of the proprietary model. None of these alternatives preserves the confidentiality of the traded security's identity.
Developers of the sequence generation programs and the corresponding generated sequences face similar security concerns in selling or licensing their products. The sequence generation programs rely on development of proprietary theoretical understanding of valuation programs (hereinafter "models") which will result in generation of more efficient sequences. The proprietary models may be developed with knowledge of the general features of the valuation programs so that the sequence generation program may be provided to owners of different valuation programs with the same characteristics. In contracting with the owner of a valuation program, the owner of the sequence generation program may divulge the proprietary models and assumptions of its sequence generation models by supplying the sequence to the user of the valuation program. By learning this information, the owner of the valuation program may simply write their own sequence generation program, thus depriving the sequence generation program owner of an opportunity to sell the program.
In many cases of practical interest, it is possible to perform the desired calculation not only by the Monte Carlo method but also by the lattice method. The lattice method is generally faster than the Monte Carlo method, and so is frequently preferred in applications where the time of calculation needs to be as short as possible. For example, in financial applications, it is desirable to compute the price of derivative securities as quickly as possible so that derivative dealers might provide clients with real-time prices; any delay may result in lost sales or trading opportunities.
Lattice methods may also be accelerated by proprietary lattice acceleration programs. However, the same secrecy considerations apply as in the case of accelerating the Monte Carlo method. The party in possession of the proprietary lattice acceleration programs will not wish to disclose these to the user of the proprietary valuation program; and the user of the valuation program will not wish to disclose the proprietary elements of the valuation program to a third party such as the developer of the proprietary lattice acceleration programs.
Therefore, a need exists for a device which enables a party to accelerate its own proprietary valuation code using a proprietary sequence generation program developed by another party without disclosing the details of the valuation code. Furthermore, a need exists for a method to allow the interfacing of a valuation code with a sequencing program to accelerate computation. Also, a need exists for an interface which enables a sequence generation program which is adaptable to a wide variety of valuation programs to be used without disclosing the models underlying the sequence generation program.